//
//  40. 组合总和II.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/6/28.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
/**
 关键信息
 candidates里有重复的元素
 每个元素在同一个集合中只能使用一次。所以去除在通一层的重合就可以了。
 横向上去重；采用排序，然后横向遍历时跳过。但这样跳过在代码上把纵向的也去除了。需要在补回来
 这个所得比较清楚 https://github.com/raojunbo/leetcode-master/blob/master/problems/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.md
 */
class Solution40 {
    var result: [[Int]] = []
    var path: [Int] = []
    var used: [Bool] = []
    func combinationSum2(_ candidates: [Int], _ target: Int) -> [[Int]] {
        let sortedCandidates = candidates.sorted()
        // false表示没有使用过
        used = Array(repeating: false, count: sortedCandidates.count)
        backTrace(sortedCandidates, target: target, start: 0)
        return result
    }
    func backTrace(_ candidates: [Int], target: Int, start: Int ) {
        if target == 0 {
            result.append(path)
            return
        }
        for i in start..<candidates.count where target - candidates[i] >= 0 {
            let item = candidates[i]
            if i > 0 && item == candidates[i - 1] && used[i - 1] == false {
                used[i] = false
                continue
            }
            path.append(item)
            used[i] = true
            backTrace(candidates, target: target - item, start: i + 1)
            used[i] = false
            path.removeLast()
        }
    }
    static func test() {
        let candidates = [10,1,2,7,6,1,5]
        let solution = Solution40()
        let result = solution.combinationSum2(candidates, 8)
        print(result)
    }
}
